//
// Created by Semir on 2020/5/25.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct LittleCmp {
    bool operator() (const int& a, const int& b) {
        return a < b;
    }
};

struct LargeCmp {
    bool operator() (const int& a, const int& b) {
        return a > b;
    }
};

priority_queue<int, vector<int>, LittleCmp> LittleRootHaep;
priority_queue<int, vector<int>, LargeCmp> LargeRootHeap;

void Insert(int num) {
    if (LittleRootHaep.empty() || num <= LittleRootHaep.top()) {
        LittleRootHaep.push(num);
    } else {
        LargeRootHeap.push(num);
    }
    if (LittleRootHaep.size() > LargeRootHeap.size() + 1) {
        LargeRootHeap.push(LittleRootHaep.top());
        LittleRootHaep.pop();
    }
    if (LargeRootHeap.size() > LittleRootHaep.size() + 1) {
        LittleRootHaep.push(LargeRootHeap.top());
        LargeRootHeap.pop();
    }
}

double GetMedian() {
    if (LittleRootHaep.size() == LargeRootHeap.size()) {
        return (double) (LittleRootHaep.top() + LargeRootHeap.top()) * 1.0 / 2;
    }
    return LittleRootHaep.size() > LargeRootHeap.size() ? LittleRootHaep.top() : LargeRootHeap.top();
}

int main() {
    vector<int> arr = {1,2,3,4,5,6,7,3,4,345,612,35,66};
    for (int i = 0; i < arr.size(); i++) {
        Insert(arr[i]);
    }
    double res = GetMedian();
    cout << res << endl;
    return 0;
}
